package leetcode.backtrace;

import java.util.ArrayList;
import java.util.List;

public class Lc131_2 {


    List<List<String>> ans = new ArrayList<>();
    boolean[][] dp;

    //动态优化先算出所有的回文字串
    public List<List<String>> partition(String s) {
        dp = new boolean[s.length()][s.length()];
        for (int j = 0; j < s.length(); j++) {
            for (int i = 0; i <= j ; i++) {
                if (i == j)
                    dp[i][j] = true;
                else {
                    if (s.charAt(i) == s.charAt(j) && ((j - i <= 2) || dp[i + 1][j - 1])) {
                        dp[i][j] = true;
                    }
                }
            }
        }
        List<String> list = new ArrayList<>();
        backTrack(s, 0, list);
        return ans;
    }

    private void backTrack(String s, int start, List<String> list) {
        if (start == s.length()) {
            ans.add(new ArrayList<>(list));
            return;
        }
        for (int i = start ; i < s.length(); i++) {
            if (dp[start][i]) {
                list.add(s.substring(start, i + 1));
                backTrack(s, i + 1, list);
                list.remove(list.size() - 1);
            }
        }
    }
}
